import problem.Problem

class Q72 extends Problem {
  def minDistance(word1: String, word2: String): Int = {
    val c = Array.fill(word1.length, word2.length)(-1)
    val w1 = word1.toArray
    val w2 = word2.toArray
    val n = edit(0, 0)(w1, w2, c)
    n
  }

  def edit(i: Int, j: Int)(
    implicit w: (Array[Char], Array[Char], Array[Array[Int]])
  ): Int = {
    val (w1, w2, c) = w
    if (i == w1.length && j == w2.length) 0 // match !
    else if (i == w1.length) w2.length - j // delete tail
    else if (j == w2.length) w1.length - i // delete tail
    else if (c(i)(j) != -1) c(i)(j)
    else {
      c(i)(j) = if (w1(i) == w2(j)) { // nothing
        edit(i + 1, j + 1)
      } else {
        1 + List(
          edit(i, j + 1), // insert
          edit(i + 1, j), // delete
          edit(i + 1, j + 1) // replace
        ).min
      }
      c(i)(j)
    }
  }

  override def test(): Unit = {
    val cases = Table(
      ("word1", "word2", "distance"),
      ("horse", "ros", 3),
      ("intention", "execution", 5)
    )

    forEvery(cases) {
      case (w1, w2, d) =>
        minDistance(w1, w2) shouldBe d
    }
  }
}
